package org.cxy.sort;

import java.util.Arrays;

// 选择排序
public class SelectSortDemo {
    public static void main(String[] args) {
        int[] arr = {80, 50, 60, 40, 70, 20};

        System.out.println("原始数组: " + Arrays.toString(arr));

        int[] sortedArr = selectSort(arr);

        System.out.println("排序后数组: " + Arrays.toString(sortedArr));
    }

    /**
     * 选择排序：对整型数组进行升序排序
     * 原理：每一轮从未排序部分中找出最小元素，将其与未排序部分的第一个元素交换
     *      从而逐步构建有序序列（从左到右）
     *
     * @param arr 待排序的数组（原地修改）
     * @return 已排序的数组
     */
    public static int[] selectSort(int[] arr) {
        // 外层循环：控制已排序部分的边界
        // i 表示当前要放置最小值的位置（即未排序部分的起始位置）
        for (int i = 0; i < arr.length - 1; i++) {
            System.out.println("第 " + (i + 1) + " 轮：寻找从索引 " + i + " 到末尾的最小值");

            // k 用于记录本轮找到的最小元素的索引
            int k = i;

            // 内层循环：在未排序部分（i+1 到 end）中寻找比 arr[k] 更小的元素
            for (int j = k + 1; j < arr.length; j++) {
                if (arr[j] < arr[k]) {
                    k = j; // 更新最小值的索引
                }
            }

            // 此时 k 是未排序部分中最小元素的索引
            // 如果 k != i，说明最小值不在当前位置，需要交换
            if (i != k) {
                // 交换 arr[i] 和 arr[k]
                int temp = arr[i];
                arr[i] = arr[k];
                arr[k] = temp;

                System.out.println("  交换 arr[" + i + "] 和 arr[" + k + "]：" +
                        Arrays.toString(arr));
            } else {
                System.out.println("  最小值已在位置 " + i + "，无需交换");
            }
        }
        return arr;
    }
}